package 剑指专题.动态规划;


/*
 * Author：江松
 * Date：2023/3/21 20:16
 *

 *哈希表：常用来统计频率、映射关系（坐标）、快速检验某个元素是否出现过等。

 * 滑动窗口：在处理滑动窗口的时候，常用双指针来解决，
 左指针维护窗口左界，右指针维护窗口右界，二者同方向不同速率移动维持窗口。
 也可以用DeQueue进行实现


 最长不含重复字符串的子字符串
 1,暴力法遍历区间，再加上校验(set降低复杂度）O(n^3)超时
 2，题解：滑动窗口问题



 2，自己想的，双指针（DP思想）+哈希表
 用哈希表统计字符出现坐标，如果后面：如aa，bcefaa重复，包含前面的串就一定重复
 那么就直接转移到后面位置。同时要注意cbabdefc，指针j只能一直往后，需要取最大值
 DP做法：
 dp(i)为以第i个无重复字符串长度(计数)
 划分：第i个字符是否重复
 转移：min(dp(i-1)+1,i-map.get(s[i[))

 */

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

public class Main8 {

    /*
    //滑动窗口
    public int lengthOfLongestSubstring (String s) {
        //记录次数
        HashMap<Character,Integer>map=new HashMap<>();
        int l=0,r=0;
        int ans=1;
        while(r<s.length()&&l<=r){
            char ch=s.charAt(r);
            if(!map.containsKey(ch)){
                map.put(ch,1);
            }else{
                map.put(ch,map.get(ch)+1);
            }
            //维护窗口，使得里面没有重复
            while(map.containsKey(ch)&&map.get(ch)>1){
                map.put(s.charAt(l),map.get(s.charAt(l))-1);
                l++;
            }
            ans=Math.max(ans,r-l+1);
            r++;
        }
        return ans;
    }
    */



    //动态规划
    public int lengthOfLongestSubstring (String s) {
        if(s==null||s.length()<1)return 0;
        int dp[]=new int[s.length()+1];
        int ans=1;
        HashMap<Character,Integer>map=new HashMap<>();
        for(int i=1;i<=s.length();++i){
            char ch=s.charAt(i-1);
            if(!map.containsKey(ch)){
                map.put(ch,1);
                dp[i]=dp[i-1]+1;
            }else{
                //重复,且还要保证是最近的因为ch坐标可能在前边
                dp[i]=Math.min(dp[i],i-map.get(ch));
                map.put(ch,i);
            }
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }

    /*
    //动态规划思想+哈希表
    public int lengthOfLongestSubstring (String s) {
        //当前字符出现的坐标
        Map<Character,Integer> map=new HashMap<>();
        int i=0,j=0;
        int ans=1;
        while(i<s.length()&&j<=i){
            char ch=s.charAt(i);
            if(!map.containsKey(ch)){
                map.put(ch,i);
            }else{
                //bug:j应该取最大值，j只会向后移动；不取最大值如果遇到与前面相同的就会回到前面
                j=Math.max(j,map.get(ch)+1);
                map.put(ch,i);
            }
            i++;
            ans=Math.max(ans,i-j+1);
        }
        return ans;
    }
    */

    public static void main(String[] args) {
        HashMap<Character,Integer>map=new HashMap<>();
        map.put('a',1);
        //null>1空指针异常
        System.out.println(map.get('b')>1);
    }


    /*
    String s;
    public boolean check(int l,int r){
        HashSet<Character>set=new HashSet<>();
        for(int i=l;i<=r;++i){
            if(set.contains(s.charAt(i))){
                return false;
            }
            set.add(s.charAt(i));
        }
        return true;
    }
    public int lengthOfLongestSubstring (String s) {
        this.s=s;
        int ans=1;
        for(int len=1;len<=s.length();++len){
            for(int l=0;l<s.length()-1;++l){
                int r=l+len-1;
                 if(r>=s.length())continue;
                if(check(l,r)){
                    ans=Math.max(ans,len);
                }
            }
        }
        return ans;
    }
    */
}
